package com.gy.algorithm.carl.backtrack;

import com.ljzn.Test;

import java.util.Arrays;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl.backtrack
 * @Author: gy
 * @Date: 2024/10/24 13:37
 * @Description:
 */
public class CanPartitionKSubsets698 {
    public static void main(String[] args) {
        Test solutionOf698 = new Test();
        System.out.println(canPartitionKSubsets(new int[]{4, 3, 2, 3, 5, 2, 1}, 4));
    }

    public static int[] numUsed;

    public static boolean canPartitionKSubsets(int[] nums, int k) {
        numUsed = new int[nums.length];
        int sum = Arrays.stream(nums).sum();
        Arrays.sort(nums);
        if (sum % k != 0 || nums[nums.length - 1] > sum / k) return false;
        return divideGroup(nums, nums.length - 1, sum / k, 0, k);
    }

    private static boolean divideGroup(int[] nums, int start, int target, int current, int k) {
        if (k == 1) return true;
        if (current == target) return divideGroup(nums, nums.length - 1, target, 0, k - 1);
        for (int i = start; i >= 0; i--) {
            if (numUsed[i] == 1 || nums[i] + current > target) continue;
            numUsed[i] = 1;
            if (divideGroup(nums, i - 1, target, nums[i] + current, k)) return true;
            numUsed[i] = 0;
            while (i > 0 && nums[i - 1] == nums[i]) i--;
        }

        return false;
    }
}
